package binarytree

type TreeNode struct {
	Val         int
	Left, Right *TreeNode
}

// 使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
// 原树是BST 右子树大于等于某节点（包括其自身）
func convertBST(root *TreeNode) *TreeNode {
	//迭代中序遍历
	sum := 0
	stack := []*TreeNode{}
	curNode := root
	for curNode != nil || len(stack) > 0 {
		for curNode != nil {
			stack = append(stack, curNode)
			// nodeStack = append(nodeStack, curNode)
			curNode = curNode.Left
		}
		curNode = stack[len(stack)-1]
		stack = stack[:len(stack)-1]

		sum += curNode.Val

		curNode = curNode.Right
	}
	//遍历结束 得到sum  再来一次遍历？
	//栈是空的，不需要重新初始化
	curNode = root
	for curNode != nil || len(stack) > 0 {
		for curNode != nil {
			stack = append(stack, curNode)
			// nodeStack = append(nodeStack, curNode)
			curNode = curNode.Left
		}
		curNode = stack[len(stack)-1]
		stack = stack[:len(stack)-1]

		curVal := curNode.Val
		curNode.Val = sum
		sum -= curVal
		curNode = curNode.Right
	}
	return root
}

//右中左
func bstToGst(root *TreeNode) *TreeNode {
	var sum int
	RightMLeft(root, &sum)
	return root
}
func RightMLeft(root *TreeNode, sum *int) *TreeNode {
	if root == nil {
		return nil
	} //终止条件，遇到空节点就返回
	RightMLeft(root.Right, sum) //先遍历右边
	temp := *sum                //暂存总和值
	*sum += root.Val            //将总和值变更
	// 中节点的处理逻辑就是让cur的数值加上前一个节点的数值。
	root.Val += temp            //更新节点值
	RightMLeft(root.Left, sum)  //遍历左节点
	return root
}
